package problem87_Scramble_String;

import java.util.Arrays;

public class SolutionUsingRecursive {
	 public boolean isScramble(String s1, String s2){
		 if(s1.equals(s2))	return true;
		 for(int i=1;i<s1.length();i++){
			 String s1Left=s1.substring(0,i);
			 String s1Right=s1.substring(i);
			 String s2Left=s2.substring(0,i);
			 String s2Right=s2.substring(i);
			 if(sameChars(s1Left,s2Left)&&sameChars(s1Right, s2Right)&&isScramble(s1Left,s2Left)&&isScramble(s1Right,s2Right))
				 return true;
			 String s2Left2=s2.substring(s2.length()-i);
			 String s2Right2=s2.substring(0,s2.length()-i);
			 if(sameChars(s1Left,s2Left2)&&sameChars(s1Right, s2Right2)&&isScramble(s1Left,s2Left2)&&isScramble(s1Right,s2Right2))
				 return true;
		 }
		return false;
	 }
	 
	 private boolean sameChars(String s1,String s2){
		 char[] s1Array=s1.toCharArray();
		 char[] s2Array=s2.toCharArray();
		 Arrays.sort(s1Array);
		 Arrays.sort(s2Array);
		 for(int i=0;i<s1Array.length;i++){
			 if(s1Array[i]!=s2Array[i])
				 return false;
		 }
		 return true;
	 }
}
